def insertionsort(arr):
    n = len(arr)
    if n <= 1: return arr
    
    for i in range(1, n):
        j = i
        while j > 0 and arr[j-1] > arr[j]:  # find position for insertion
            arr[j-1], arr[j] = arr[j], arr[j-1]  # swap
            j -= 1
    
    return arr


if __name__ == "__main__":
    print(insertionsort([9, 2, 8]))
    print(insertionsort([3, 6, 0, 4]))
    print(insertionsort([1, 8, 7, 3, 6, 0, 4]))
